In wireless communication networks, neighbour discovery may be performed by devices such as video projectors, laptops, mobile phones, digital tablets, or the like.
Wireless ad hoc networks comprise WPAN (“Wireless Personal Area Networks”), WLAN (“Wireless Local Area Networks”), WMAN (“Wireless Metropolitan Area Network”), WWAN (“Wireless Wide Area Networks”), wireless sensor networks etc. The number of applications based on this type of network is increasing. Applications may be video surveillance, video multi-projection, disaster recovery, etc.
Wireless ad hoc network schemes frequently rely on a mesh communication scheme, which allows collaborating devices to relay information from one device to another across multiple wireless links. Each device has the ability to operate in both transmit and receive modes, either simultaneously or alternately.
Typically, such wireless mesh networks are setup in a self-organizing way, which means that the network devices do not require a pre-existing infrastructure for performing device discovery along with medium access scheme determination and setup.
Some wireless ad-hoc mesh networks, even though being self-organizing, may have deterministic topologies. The devices remain static (for example a video surveillance network or a wireless sensor network installed in an office or a housing building). Such wireless networks may be of the IEEE 802.11 WPAN or WLAN type.
For example, disaster recovery networks are a type of wireless self-organizing networks. Such type of networks is deployed on wide terrains wherein wireless devices are assigned respective restricted operation areas that are arranged symmetrically and of equal sizes. Multi-projection systems, are another type of wireless self-organizing networks wherein spatial topology is typically setup according to an n×m matrix arrangement.
Some wireless networks, even though being “ad-hoc” in the sense that their actual spatial arrangement is not predetermined, may nevertheless be setup according to some predefined network model settings. In other words, even though their actual spatial topology is not known by the network devices, such devices may intuit it at some point. For example, in case the devices are spatially arranged according to an array topology, each device knows that it is surrounded by up to eight other devices. Each device may thus intuit the positioning of its potential neighbour devices. In the same way, a video projector device belonging to a matrix of video projectors may not know the actual size of the matrix. In case the only communications allowed in the network are communications between devices belonging to the same line or column, a device knows that its potential neighbour devices are located at 0°, 90°, 180° and 270° directions.
In a wireless self-organizing network, one given device may be able to communicate only with a limited set of devices. Such devices are commonly referred to as “neighbour devices”. In the absence of a master coordinator device, at least upon system start up, each device shall first discover its own neighbour devices before any medium access scheme and associated routing is set up. The process for a device to identify all its neighbours is usually referred to as “neighbour discovery process”.
Typically, a device that wishes to discover its neighbour devices shall transmit, in broadcast mode in most cases, a probe message and wait for the reception of a probe response message issued by a neighbour device (which has received the probe message). Such probe handshake shall be robust to frame collisions and interferences, which are most likely to occur in an ad-hoc wireless network. Indeed, the interferences and collisions during the “neighbour discovery process” make the process last longer. In order to mitigate the impact of frame collisions and network interferences, probe messages and response frames to/from different neighbours are typically generated repeatedly and transmitted after random delays.
This neighbour discovery approach, also referred to as the “random access neighbour discovery scheme”, has been specified for the ad-hoc mode of IEEE 802.11 standards as well as for generic mobile ad hoc networks (“MANETs”) by the Internet Engineering Task Force (“IETF”) MANET working group, and is found in many well-known state of the art algorithms, like for instance the “birthday” algorithm or the “coupon collector” algorithm. These algorithms rely on a collision model while requiring the devices to randomly alternate transmit and receive modes, so as to ensure the completion of the handshake discovery process. However, such discovery schemes require a significant amount of contention time slots to guarantee successful discovery, which results in a significant latency before discovery process completion, along with significant bandwidth overhead.
Document WO 2012/131512 A1 discloses a group-based discovery scheme for reducing the risks of interferences and frame collisions during the neighbour discovery process.
The group-based discovery scheme is based on the dynamic and iterative selection of a neighbour discovery proxy, amongst a reference group of network devices, by a centralized coordinator device. The selected proxy device is in charge of both performing discovery process handshake(s) with its neighbour device(s) and reporting the results of this discovery process to the centralized coordinator device. Said centralized coordinator device shall then associate the newly discovered neighbour devices to the reference group of network devices and select a new proxy device inside the reference group until a predefined number of devices were discovered.
Such method requires a network device to be selected for acting as a centralized coordinator device in charge of driving the discovery process. This may considered as in contradiction with the self-organizing network approach.
Moreover, such method implies that only one device at a time is performing neighbour discovery, which may increase the overall discovery process latency.
Thus, there is a need for enhancing neighbour device discovery is wireless communication networks.
The present invention lies within this context.